/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/word-ladder-ii
   @Language: C++
   @Datetime: 19-08-30 13:37
   */

// Method 1, bfs, Time 1236ms, Space 113MB
class Solution {
public:
	vector<vector<string>> findLadders(string begin, string end, vector<string>& wordList) {
		unordered_set<string> dict(wordList.begin(),wordList.end());
		queue<pair<string,vector<string> > > q({{begin,{}}});
		vector<vector<string> > vs;
		for(; q.size() && vs.size()==0;){
			unordered_set<string> dels;
			for(int size=q.size(); size--; q.pop()){
				string &word=q.front().first;
				q.front().second.push_back(word);
				if(word==end){
					vs.push_back(q.front().second);
					continue;
				}
				for(int i=0; i<word.length(); ++i){
					for(char ch='a'; ch<='z'; ++ch){
						string s=word;
						if(s[i]==ch) continue;
						s[i]=ch;
						if(dict.count(s)==0) continue;
						q.push({s,q.front().second});
						dels.insert(s);
					}
				}
			}
			for(const string &s:dels)
				dict.erase(s);
		}
		return vs;
	}
};


// Method 2, trace dfs, Time 156ms, Space 22.5MB
class Solution {
	void dfs(unordered_map<string,unordered_set<string> > &trace, const string &last, vector<string> path, vector<vector<string> > &vs){
		path.push_back(last);
		if(trace.count(last)==0){
			reverse(path.begin(),path.end());
			vs.push_back(path);
			return;
		}
		for(const string &word:trace[last])
			dfs(trace,word,path,vs);
	}
public:
	vector<vector<string>> findLadders(string begin, string end, vector<string>& wordList) {
		unordered_set<string> dict(wordList.begin(),wordList.end());
		if (dict.count(end)==0) return {};
		unordered_map<string,unordered_set<string> > trace;
		unordered_set<string> q={begin}, dels;
		for(; q.size() && trace.count(end)==0; q=dels){
			for(const string &word:q)
				dict.erase(word);
			dels.clear();
			for(const string &word:q){
				for(int i=0; i<word.length(); ++i){
					string s=word;
					for(char ch='a'; ch<='z'; ++ch){
						if(word[i]==ch) continue;
						s[i] = ch;
						if(dict.find(s)==dict.end()) continue;
						trace[s].insert(word);
						dels.insert(s);
					}
				}
			}
		}
		if(trace.size()==0) return {};
		vector<vector<string> > result;
		dfs(trace,end,{},result);
		return result;
	}
};
